package ShortestPath;

import java.util.LinkedList;
import java.util.Queue;

public class NearestExitFromEntranceInMaze {
    public int nearestExit(char[][] maze, int[] e) {
        // 辅助向量数组
        int[] dx = { 1, -1, 0, 0 };
        int[] dy = { 0, 0, 1, -1 };

        int m = maze.length; // 对应 x 坐标
        int n = maze[0].length; // 对应 y 坐标

        // 辅助布尔访问数组
        boolean[][] visit = new boolean[m][n];

        // 记录每条 "路" 所走的步伐, 每层是 1 步
        int step = 0;

        // 用队列保存 "路" 坐标
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { e[0], e[1] });
        visit[e[0]][e[1]] = true;

        while (!queue.isEmpty()) {
            // 走到这意味着要遍历下一层节点, 也就是准备沿着每条路向前走一步
            // 因此 step++
            step++;

            // size 记录当前层节点的下一层节点个数
            // 保证每次都是一层节点全部出队列
            int size = queue.size();
            while (size != 0) {
                // 取出当前层节点
                int[] point = queue.poll();
                // 分解点坐标
                int Ox = point[0];
                int Oy = point[1];

                // 遍历下一层节点, offer进 "路" 坐标
                for (int i = 0; i < 4; i++) {
                    int x = Ox + dx[i];
                    int y = Oy + dy[i];

                    if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && visit[x][y] == false) {
                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) {
                            // 如果该点在边缘, 说明已经找到出口了
                            // 这道题只要走到出口的位置就可以, 但 step 已经 ++ 过了
                            // 因此直接返回即可
                            return step;
                        }

                        // 没有到边缘, 那就继续走
                        queue.offer(new int[] { x, y });
                        visit[x][y] = true;
                    }
                }
                size--;
            }
        }

        // 走到这, 说明不存在路径
        return -1;
    }
}
